package leetcode.primary.array;

import java.awt.*;

/**
 * TODO 买卖股票的最佳时机 II 定一个数组 prices ，其中prices[i] 是一支给定股票第 i 天的价格。
 * 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
 * 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
 * 示例输入: prices = [7,1,5,3,6,4]
 * 输出: 7
 *
 * @author david
 * @version 1.0
 * @date 2021/4/22 9:20
 */
public class MaxProfit {
    public static void main(String[] args) {
        int[] prices = new int[]{7, 1, 5, 3, 6, 4};
        System.out.println(maxProfit(prices));
        System.out.println(maxProfit2(prices));
    }

    /**
     * 贪心算法 基础上的优化
     * 时间复杂度 O(n) 空间复杂度O(1)
     * @param prices
     * @return
     */
    static int maxProfit2(int[] prices){
        int result=0;
        for (int i=1;i<prices.length-1;i++){
            //原数组中如果后一个减去前一个是正数，说明是上涨的，
            //我们就要累加，否则就不累加
            result+=Math.max(prices[i]-prices[i-1],0);
        }
        return result;
    }
    /**
     * 贪心算法
     * @param prices
     * @return
     */
    static int maxProfit(int[] prices) {
        if (prices == null || prices.length < 2)
            return 0;
        int total = 0, index = 0, length = prices.length;
        while (index < length) {
            //如果股票下跌就一直找，直到找到股票开始上涨为止
            while (index < length - 1 && prices[index] >= prices[index + 1])
                index++;
            //股票上涨开始的值，也就是这段时间上涨的最小值
            int min = prices[index];
            //一直找到股票上涨的最大值为止
            while (index < length - 1 && prices[index] <= prices[index + 1])
                index++;
            //计算这段上涨时间的差值，然后累加
            total += prices[index++] - min;
        }
        return total;
    }
}
